home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / convex_hull.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  3KB  |  177 lines
  1. #include <LEDA/plane.h>
  2. #include <LEDA/graph.h>
  3. #include <LEDA/window.h>
  4.  
  5.  
  6. struct p_edge {
  7.  
  8. segment   s;
  9. list_item it;
  10.  
  11. };
  12.  
  13. typedef p_edge* p_edge_ptr;
  14.  
  15.  
  16.  
  17.  
  18. GRAPH<p_edge_ptr,int> DAG;
  19. list<node>            POL;
  20.  
  21.  
  22.  
  23. node NEW_NODE(segment s)
  24. { p_edge_ptr p = new p_edge;
  25.   p->s =s;
  26.   return DAG.new_node(p);
  27.  }
  28.  
  29.  
  30.  
  31.  
  32. node next_segment(segment s, node v )
  33. { node u = nil;
  34.   node w;
  35.   point Q;
  36.   forall_adj_nodes(w,v)
  37.     if (s.intersection(DAG[w]->s,Q)) 
  38.     { u = w;
  39.       break;
  40.      }
  41.   DAG.init_adj_iterator(v);
  42.   return u;
  43. }
  44.  
  45.  
  46.  
  47. main()
  48. { 
  49.  
  50.   window W;
  51.  
  52.   W.init(0,1000,0);
  53.  
  54.  
  55.   point A,B,C;
  56.  
  57.   W >> A; W << A;
  58.   W >> B; W << B;
  59.   W >> C; W << C;
  60.  
  61.   // we start with a triangle
  62.  
  63.   segment sa(A,B);
  64.   segment sb(B,C);
  65.   segment sc(C,A);
  66.  
  67.   W << sa << sb << sc;
  68.  
  69.   if (sa.angle(sb) < 0) 
  70.   { sa = segment(A,C);
  71.     sb = segment(C,B);
  72.     sc = segment(B,A);
  73.    }
  74.  
  75.   node root = NEW_NODE(segment(A,A));
  76.   node    a = NEW_NODE(sa);
  77.   node    b = NEW_NODE(sb);
  78.   node    c = NEW_NODE(sc);
  79.  
  80.   //DAG edges
  81.  
  82.   DAG.new_edge(root,a,0);
  83.   DAG.new_edge(root,b,0);
  84.   DAG.new_edge(root,c,0);
  85.  
  86.   //POL is initialized to triangle (A,B,C);
  87.  
  88.   DAG[a]->it = POL.append(a);
  89.   DAG[b]->it = POL.append(b);
  90.   DAG[c]->it = POL.append(c);
  91.  
  92.   double x = (A.xcoord() + B.xcoord() + C.xcoord())/3;
  93.   double y = (A.ycoord() + B.ycoord() + C.ycoord())/3;
  94.  
  95.   point I(x,y);
  96.  
  97.   point P;
  98.  
  99.   while (W>>P)
  100.   { W << P;
  101.  
  102.     point   Q;
  103.  
  104.     segment S(P,I);
  105.  
  106.     node v = root;
  107.  
  108.     while (v!=nil && DAG.outdeg(v)!=0) v = next_segment(S,v);
  109.  
  110.     if (v==nil) continue;
  111.  
  112.      list_item it;
  113.  
  114.  
  115.      point   rtouch  = DAG[v]->s.start();
  116.      segment rtangent(P,rtouch);
  117.      node    w = v;
  118.  
  119.      it = DAG[w]->it;
  120.      while (rtangent.angle(DAG[w]->s) <= 0) 
  121.      { 
  122.        it = POL.cyclic_succ(it);
  123.        w = POL[it];
  124.        rtouch   = DAG[w]->s.start();
  125.        rtangent = segment(P,rtouch);
  126.       }
  127.  
  128.      point   ltouch   = DAG[v]->s.end();
  129.      segment ltangent(ltouch,P);
  130.      node    u = v;
  131.  
  132.      it = DAG[u]->it;
  133.      while (ltangent.angle(DAG[u]->s) >= 0) 
  134.      { it = POL.cyclic_pred(it);
  135.        u = POL[it];
  136.        ltouch   = DAG[u]->s.end();
  137.        ltangent = segment(ltouch,P);
  138.       }
  139.  
  140.  
  141.      node x = NEW_NODE(ltangent);
  142.      node y = NEW_NODE(rtangent);
  143.  
  144.      // draw tangents
  145.  
  146.      W << ltangent << rtangent;
  147.  
  148.  
  149.      it = POL.cyclic_succ(DAG[u]->it);
  150.      
  151.      while (it != DAG[w]->it)
  152.      { list_item i = it;
  153.        it = POL.cyclic_succ(it);
  154.        DAG.new_edge(POL[i],x);
  155.        DAG.new_edge(POL[i],y);
  156.        POL.del(i);
  157.       }
  158.      
  159.      DAG[x]->it = POL.insert(x,it,before);
  160.      DAG[y]->it = POL.insert(y,it,before);
  161.  
  162.  
  163.    }
  164.  
  165.   W.clear();
  166.   W.set_line_width(3);
  167.  
  168.   node v;
  169.  
  170.   forall(v,POL) W << DAG[v]->s;
  171.  
  172.   W.read_mouse();
  173.  
  174.  return 0;
  175. }
  176.  
  177.